#! /usr/bin/python

#v 2.1

import random
import threading

class pool_team:
	number=""
	last=""
	history=[]
	
	def __init__(self, n, h):
		self.number=n
		if type(h) != list:
			self.history = [h]
		else:
			self.history = h
		if len(self.history) > 0:
			self.last = self.history[len(self.history)-1]

	def add_table(self, t):
		self.history.append(t)
		self.last = t

	def __str__(self):
		global names
		s = ''
		'''
		if names != {}:
			if self.number < 10:
				s += str(names[self.number]) + " : "
			else:
				s += str(names[self.number]) + ": "
		'''
		for h in self.history:
			h = h.split('-')
			s += ''
			for tmp in h:
				s += str(tmp) + "&"
				
			s = s[:-1]
			s += ", "
		s = s[:-2]
		return s

	def close(self):
		self.number=""
		self.last=""
		self.history=[]

class league:
	teams=[]

	def __init__(self):
		pass

	def __str__(self):
		s = ''
		for t in self.teams:
			s += str(t) + "\n"
		return s[:-1]

	def __getitem__(self, item):
		if type(item) is str:
			return self.teams[item]
		else:
			return self.teams[item-1]

	def add_team(self, t):
		self.teams.append(t)

	def clear(self):
		for t in self.teams:
			t.close()
		self.teams=[]

# globals
schedule={}
week_dates=[]
bye_team = -1
names={}
assignments={}
available=[]
taken={}
group_a = []
group_b = []
group_c = []
bad_thresh = 0
longest_name = ''

def clear_globals():
	global schedule, available, taken, group_a, group_b, group_c
	schedule = {}
	names = {}
	available = []
	taken = {}
	group_a = []
	group_b = []
	group_c = []

def read():
	global schedule, names, available, taken, group_a, group_b, group_c, bad_thresh, longest_name, week_dates, bye_team
	f = open('in.txt')
	build_schedule = False
	build_available = False
	build_names = False
	build_bad_thresh = False
	week = 1
	for line in f.readlines():
		if line.startswith('#'):
			continue
		elif 'schedule' in line or build_schedule:
			# read in schedule
			if 'schedule' in line:
				build_schedule = True
				continue
			if 'end' in line:
				build_schedule = False
				continue
			l = []
			burn_index = 0
			for t in line.split():
				if burn_index < 5:
					if burn_index == 2:
						week_dates.append(t)
					burn_index += 1
					continue
				l.append(t)
			schedule[week] = l
			week += 1
		elif 'available' in line or build_available:
			# read in available and taken
			# divide into 3 groups
			if 'available' in line:
				build_available = True
				continue
			if 'end' in line:
				build_available = False
				continue
			available = line.split()
			i = 1
			for a in available:
				taken[a] = 0
				if i % 3 == 1:
					group_a.append(a)
				elif i % 3 == 2:
					group_b.append(a)
				else:
					group_c.append(a)
				i += 1
		elif 'names' in line or build_names:
			# read in team names
			if 'names' in line:
				build_names = True
				continue
			if 'end' in line:
				build_names = False
				continue
			names[int(line.split(':')[0])] = line.split(':')[1].strip()
			if len(line.split(':')[1].strip()) > len(longest_name):
				longest_name = line.split(':')[1].strip()
			if line.split(':')[1].strip == 'bye':
				bye_team = int(line.split(':')[0].strip())
		elif 'bad_thresh' in line or build_bad_thresh:
			if 'bad_thresh' in line:
				build_bad_thresh = True
				continue
			if 'end' in line:
				build_bad_thresh = False
				continue
			bad_thresh = int(line.split()[0])
	f.close()
	pad_names()

def pad_names():
	global longest_name, names
	for key, name in names.iteritems():
		names[key] = name.ljust(len(longest_name))

def assign_names():
	global schedule, names, assignments
	if names == {}:
		return
	_assignments = {}
	for num, name in names.iteritems():
		for week, sched in schedule.iteritems():
			for match in sched:
				index = schedule[week].index(match)
				schedule[week][index] = str.replace(schedule[week][index], str(num), name)
		_assignments[name] = str(assignments[int(num)]) + "\n"

	assignments = _assignments


def print_output():
	global schedule, assignments, week_dates
	f = open('out.html', 'w')
	f.write('<html><table border="1">')
	f.write('<tr><td></td>')
	for week, matches in schedule.iteritems():
		f.write('<td align=center>&nbsp&nbsp %s &nbsp&nbsp</td>' %(week_dates[int(week)-1][:-5]))
	f.write('</tr>')
	i = 0
	for team, assign in assignments.iteritems():
		if i % 2:
			style = 'style="background-color:silver"'
		else:
			style = ''
		f.write('<tr><td align=center %s>%s</td>' %(style, team))
		for a in assign.split(', '):
			f.write('<td align=center %s>&nbsp&nbsp %s &nbsp&nbsp</td>' %(style, a))
		f.write('</tr>')

		i += 1

	f.write('</table></html>')
	f.close()

def init_teams(num_teams):
	teams = league()
	if len(teams.teams) != 0:
		teams.clear()
	for n in range(0,num_teams):
		teams.add_team(pool_team(n+1, []))
	return teams

def pick_group(team1, team2):
	global group_a, group_b, group_c

	if team1.last == "" or team2.last == "":
		return ""

	if team1.last in group_a:
		t1_last = group_a
	elif team1.last in group_b:
		t1_last = group_b
	elif team1.last in group_c:
		t1_last = group_c

	if team2.last in group_a:
		t2_last = group_a
	elif team2.last in group_b:
		t2_last = group_b
	elif team2.last in group_c:
		t2_last = group_c
		
	# last group is the same
	if t1_last == group_a and t2_last == group_a:
		return [group_b, group_c]
	if t1_last == group_b and t2_last == group_b:
		return [group_a, group_c]
	if t1_last == group_c and t2_last == group_c:
		return [group_a, group_b]


	# last group is different
	if (t1_last == group_a and t2_last == group_b) or (t1_last == group_b and t2_last == group_a):
		return group_c
	if (t1_last == group_a and t2_last == group_c) or (t1_last == group_c and t2_last == group_a):
		return group_b
	if (t1_last == group_b and t2_last == group_c) or (t1_last == group_c and t2_last == group_b):
		return group_a

def least_frequent(group, team1, team2):
	freq = {}
	for table in available:
		freq[table]=0
	
	for table in team1.history:
		freq[table] += 1
	for table in team2.history:
		freq[table] += 1

	choice = -1
	for g in group:
		if choice == -1:
			choice = g
		elif type(g) != list:
			if freq[g] < freq[choice]:
				choice = g  
		else:
			# there are 2 groups to choose from, each group has 2 tables
			old_choice = choice
			for x in g:
				for y in old_choice:
					if freq[x] < freq[y]:
						choice = x

	return choice

def pick_table(team1, team2):
	# find the new group
	new_group = pick_group(team1, team2)

	# find which table in that group
	# if all group tables are taken, wait for later and take whatever is left based on freq
	if int(team1.number) == -1:
		least_used_in_gropu = least_frequent(new_group, team2, team2)
	elif int(team2.number) == -1:
		least_used_in_gropu = least_frequent(new_group, team1, team1)
	else:
		least_used_in_group = least_frequent(new_group, team1, team2)
	
	# all of group was taken
	# or first week so nothings used
	#
	# this returns teams instead of tables, but that is 
	# so that they can be randomly assigned the first week
	if least_used_in_group == -1:
		return [team1, team2], 1

	# this means a team played on that table last week
	if least_used_in_group == team1.last or least_used_in_group == team2.last:
		return [team1, team2], 1

	return [least_used_in_group], 0

def go(num_weeks, teams):
	for week in range(1, num_weeks+1):
		retry = []
		for x in taken:
			taken[x] = 0
		for match in schedule[week]:
			split = match.split('-')
			table, wait = pick_table(teams[int(split[0])], teams[int(split[1])])
			if wait:
				#add to try-again list
				retry.append(table)
				continue
			else:
				table = table[0]
				if type(table) != list:
					if taken[table] == 0:
						taken[table] = 1
						teams[int(split[0])].add_table(table)
						teams[int(split[1])].add_table(table)
					else:
						retry.append((teams[int(split[0])], teams[int(split[1])]))
				else:
					assigned = False
					num_tries = 0
					while not assigned:
						if num_tries > 10:
							num_taken = 0
							for t in table:
								if taken[t]:
									num_taken += 1
							if num_taken == len(table):
								retry.append((teams[int(split[0])], teams[int(split[1])]))
							assigned = True
						num_tries += 1
						i = random.randrange(0, len(table))
						t = table[i]
						if taken[t] == 0:
							taken[t] = 1
							teams[int(split[0])].add_table(t)
							teams[int(split[1])].add_table(t)
							assigned = True

		for r in retry:
			assigned = False
			while not assigned:
				i = random.randrange(0, len(taken))
				if taken[available[i]] == 0:
					taken[available[i]] = 1
					r[0].add_table(available[i])
					r[1].add_table(available[i])
					assigned = True

	return teams

def analyze(teams, table_limit):
	global taken, bye_team
	if teams == []:
		return 99
	# total_bad is the number of times a team
	# plays on a table more than table_limit times
	# or a team doesn't play on a table at all
	total_bad = 0
	for t in teams:
		if int(t.number) == -1:
			continue
		stats = {}
		for tmp in taken:
			stats[tmp] = 0
		for i in range(0, len(t.history)):
			try:
				if t.history[i] == t.history[i+1] == t.history[i+2]:
					return 100
			except:
				pass
		for h in t.history:
			stats[h] += 1
		for s in stats:
			if int(stats[s]) > int(table_limit):
				#total_bad += 1
				return 1000
			if int(stats[s]) == 0: 
				# a team never played on a table
				# this makes sure everyone plays
				# everywhere at leaset once
				return 10
	return total_bad

def run():
	global schedule, bad_thresh, names, available, assignments
	read()
	num_weeks=13
	res = 10
	while res > 0:
		base_teams = init_teams(len(names))
		read()
		teams = go(len(schedule), base_teams)
		res = analyze(teams, bad_thresh)
		#print res
		if res == 0:
			assignments = teams
			assign_names()
			print_output()
			break
		base_teams.clear()
		clear_globals()
	raise Exception, 'Finished'

run()
